package com.hgx.algorithm.base.problem;

import com.hgx.algorithm.base.utils.ArraySortUtil;

/**
 * 题目2：荷兰国旗问题
 * 给定一个数组arr和一个数num，请把小于number的数放在数组的左边，等于number的数放在数组的中间，大于number的数放在数组的右边。
 * 要求额外空间复杂度O(1),时间复杂度O(N)
 */
public class ProblemTow {

    public static void main(String[] args) {
        System.out.println("给定一个数组arr和一个数num，请把小于等于number的数放在数组的左边，等于number的数放在数组的中间，大于number的数放在数组的右边。");
//        int[] arr = ArraySortUtil.generateRandomArray(20, 50);
        int[] arr = new int[]{1, 7, -10, 9, 0, 0, -16, -3, 6, 1, 7, -12, 0, 67};
        ArraySortUtil.print(arr);
        sort(arr, 0, arr.length - 1, 0);
        ArraySortUtil.print(arr);
    }

    /**
     * 实现：数组arr和一个数num，小于number的数放在数组的左边，等于number的数放在数组的中间，大于number的数放在数组的右边。
     *
     * @param arr    需要排序的数组
     * @param left   需要排序段的左边坐标
     * @param right  需要排序段的右1边坐标
     * @param number 排序的基准数
     */
    public static void sort(int[] arr, int left, int right, int number) {
        //小于区域的坐标
        int less = left - 1;
        //大于区域的坐标
        int more = right + 1;
        //数组的当前位置
        int position = left;
        while (position < more) {
            if (arr[position] < number) {
                ArraySortUtil.swap(arr, position++, ++less);
            } else if (arr[position] > number) {
                ArraySortUtil.swap(arr, position, --more);
            } else {
                position++;
            }
        }

    }


}
